Big-omega notation（大 Ω 记号）是算法与复杂度分析中的一种渐近下界表示法：如果对足够大的输入规模 \(n\)，函数 \(f(n)\) 至少以某个常数倍的 \(g(n)\) 的速度增长，则记为
\[ f(n)=\Omega(g(n)). \]
常用来表达“运行时间/空间在最坏情况下至少不会比 \(g(n)\) 更快（更小）”。
/b om noten/
For comparison-based sorting, the time complexity is Ω(n log n).
对于基于比较的排序，时间复杂度的下界是 Ω(n log n)。
Even if the average case is fast, the algorithm still has Ω(n) time in the worst case due to nested scans.
即使平均情况很快，由于嵌套扫描，这个算法在最坏情况下仍然有 Ω(n) 的时间下界。
“Big-omega”里的 Ω 来自希腊字母 Omega（欧米伽），在数学中常用作符号。Landau 记号（渐近记号）体系里常用 O、Ω、Θ 来描述函数增长的上界、下界与紧确；该用法在计算机科学中被广泛采用，并通过经典算法教材与 Donald Knuth 等人的著作传播开来。
Select Language